//
// Created by ASUS on 2024/7/3/星期三.
//
/*
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000
s 只包含小写英文字母。
 */
#include <bits/stdc++.h>
using namespace std;
bool checkPartitioning(string s) {
	int n = s.length();
	vector<vector<bool>> f(4, vector<bool>(n + 1)); // f[i][j]代表s[0:j)能不能分割成i段
	f[0][0]=true;
	vector<vector<int>> g(n, vector<int>(n, true)); // g[i][j]->s[i:j]是否是回文串
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i + 1; j < n; ++j) {
			g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
		}
	}
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= n; j++) {
			for (int L = j - 1; L >= 0; L--) {
				if (g[L][j - 1]) f[i][j] = f[i][j] | f[i-1][L];
			}
		}
	}
	return f[3][n];
}